#!/usr/bin/env python
# -*- coding: utf8 -*-
#-------------------------------------------------------------------------------
# Name:        compiler.py
# Purpose:      use python to write a compiler.
#
# Author:      iori
#
# Created:     01/11/2014
# Copyright:   (c) iori 2014
# Licence:     GPLv3
#-------------------------------------------------------------------------------
import re
from collections import namedtuple
import types
import operator
import unittest



Token = namedtuple('Token', ['type', 'value'])
token_specification = [
    ('NUM', r'\d+'),
    ('PLUS', r'\+'),
    ('MINUS', r'\-'),
    ('TIMES', r'\*'),
    ('DIVEDE', r'/'),
    ('WS', r'\s+')
    ]

master_re = re.compile('|'.join('(?P<{}>{})'.format(*pair) \
                        for pair in token_specification))

def tokenize(text):
    ''' word analysis '''
    return (Token(m.lastgroup, m.group()) for m in master_re.finditer(text) \
                if m.lastgroup != 'WS')


def parse(tokens):
    '''
    expr ::= term {+|- term}*
    term ::=  factor {*|/ factor}*
    factor ::= NUM
    we define `term` and `factor` is to ensure * / prior to + -
    '''
    lookahead, current = next(tokens, None), None
    def accept(*tks):
        nonlocal lookahead, current  # python 3
        if lookahead and lookahead.type in tks:
            lookahead, current = next(tokens, None), lookahead
            return True

    def factor():
        if accept('NUM'):
            return Num(int(current.value))
        else:
            raise SystemError()

    def term():
        left = factor()
        while accept('TIMES', 'DIVIDE'):
            left = BinOp(current.value, left)
            right = factor()
            left.right = right
        return left

    def expr():
        left = term()
        while accept('PLUS', 'MINUS'):
            left = BinOp(current.value, left)
            right = term()
            left.right = right
        if lookahead is None:
            return left
        raise SystemError() # here, not a valid expression
    return expr()


class Node(object):
    _fields = []
    def __init__(self, *nkw):
         list(map (lambda k, v: setattr(self, k, v), self._fields, nkw))

class BinOp(Node):
    _fields = ['op', 'left', 'right']

class Num(Node):
    _fields = ['value']

OP_MAPPER = {'+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': operator.floordiv
            }

class NodeVisitor(object):

    def visit(self, node):
        return getattr(self, 'visit_{}'.format(type(node).__name__))(node)

    def genvisit(self, node):
        result = getattr(self, 'visit_{}'.format(type(node).__name__))(node)
        if isinstance(result, types.GeneratorType):
            result = yield from result  # delegate to sub generator
        return result

class Evaluator(NodeVisitor):

    def visit_BinOp(self, node):
        return OP_MAPPER[node.op](self.visit(node.left), self.visit(node.right))

    def visit_Num(self, node):
        return node.value

class Evaluator2(NodeVisitor):
    def visit_BinOp(self, node):
        lv = yield node.left
        rv = yield node.right
        return OP_MAPPER[node.op](lv, rv)

    def visit_Num(self, node):
        return node.value

    def visit(self, node):
        ''' wield, but success.
        '''
        stack = [self.genvisit(node)]
        val = None
        while stack:
            try:
                node = stack[-1].send(val)
                stack.append(self.genvisit(node))
                val = None
            except StopIteration as e: # factor, term ,expr done.
                val = e.value
                stack.pop()
        return val

def evaluater3(tree):
    ''' 表达式求值 '''
    stack = []
    node = tree
    v = 0
    while True:
        if isinstance(node , Num):
            v = node.value
            while stack and isinstance(stack[-1], int):
                opr2 = stack.pop()
                op = stack.pop().op
                v = OP_MAPPER[op](v, opr2)
            if not stack: break
            node = stack[-1].right
            stack.append(v)
        else:
            stack.append(node)
            node = node.left
    return v

def post_order(tree):
    stack = []
    node = tree
    def print_node(node):
        if isinstance(node, Num):
            print(node.value, end='->')
        else:
            print(node.op, end='->')

    while True:
        if isinstance(node, Num):
            print_node(node)
            while stack and node == stack[-1].right:
                node = stack.pop()
                print_node(node)
            if stack:
                node = stack[-1].right
            else:
                break
        else:
            stack.append(node)
            node = node.left
    print('\n')

class TestMe(unittest.TestCase):

    def test_parse(self):
        exps = ['3 + 2 * 5', '2 * 2 + 2 +3']
        for exp in exps:
            print('match for : ', exp)
            tokens = tokenize(exp)
            parse(tokens)

    def test_Num(self):
        n = Num(3)
        self.assertEqual(3, n.value)

    def test_BinOP(self):
        op = BinOp('+', 2, 3)
        self.assertEqual(['+', 2, 3], [op.op, op.left, op.right])

    def test_Evaluator(self):
        exps = ['3 + 2 * 5', '2 * 2 + 2 +3']
        vals = [13, 9]
        cal = Evaluator()
        for v, exp in zip(vals, exps) :
            tokens = tokenize(exp)
            tree = parse(tokens)
            res = cal.visit(tree)
            self.assertEqual(v, res)

    def test_Evaluator2(self):
        exps = ['3 + 2 * 5', '2 * 2 + 2 +3']
        vals = [13, 9]
        cal = Evaluator2()
        for v, exp in zip(vals, exps) :
            tokens = tokenize(exp)
            tree = parse(tokens)
            res = cal.visit(tree)
            self.assertEqual(v, res)

    def test_evaluate3(self):
        exps = ['3 + 2 * 5', '2 * 2 + 2 +3']
        vals = [13, 9]
        for v, exp in zip(vals, exps) :
            tokens = tokenize(exp)
            tree = parse(tokens)
            res = evaluater3(tree)
            self.assertEqual(v, res)

    def test_post_order(self):
        exps = ['3 + 2 * 5', '2 * 2 + 2 +3']
        vals = [13, 9]
        for v, exp in zip(vals, exps) :
            tokens = tokenize(exp)
            tree = parse(tokens)
            post_order(tree)

    def test_hurge_expr(self):
        expr = ' + '.join(str(_) for _ in range(1000))
        tokens = tokenize(expr)
        tree = parse(tokens)
        cal1 = Evaluator()
        cal2 = Evaluator2()
        with self.assertRaises(RuntimeError):
            cal1.visit(tree)
        print('result: ', cal2.visit(tree))


if __name__ == '__main__':
    unittest.main()
